Maximizing Expected Utility for Stochastic Combinatorial Optimization Problems

摘要

We study the stochastic versions of a broad class of combinatorial problemswhere the weights of the elements in the input dataset are uncertain. The classof problems that we study includes shortest paths, minimum weight spanningtrees, and minimum weight matchings, and other combinatorial problems likeknapsack. We observe that the expected value is inadequate in capturingdifferent types of {\em risk-averse} or {\em risk-prone} behaviors, and insteadwe consider a more general objective which is to maximize the {\em expectedutility} of the solution for some given utility function, rather than theexpected weight (expected weight becomes a special case). Under the assumptionthat there is a pseudopolynomial time algorithm for the {\em exact} version ofthe problem (This is true for the problems mentioned above), we can obtain thefollowing approximation results for several important classes of utilityfunctions: (1) If the utility function $\uti$ is continuous, upper-bounded by aconstant and $\lim_{x\rightarrow+\infty}\uti(x)=0$, we show that we can obtaina polynomial time approximation algorithm with an {\em additive error}$\epsilon$ for any constant $\epsilon>0$. (2) If the utility function $\uti$ isa concave increasing function, we can obtain a polynomial time approximationscheme (PTAS). (3) If the utility function $\uti$ is increasing and has abounded derivative, we can obtain a polynomial time approximation scheme. Ourresults recover or generalize several prior results on stochastic shortestpath, stochastic spanning tree, and stochastic knapsack. Our algorithm forutility maximization makes use of the separability of exponential utility and atechnique to decompose a general utility function into exponential utilityfunctions, which may be useful in other stochastic optimization problems.